package Lee_code;

import java.util.*;

/**
 * @author blh
 * @date 2024年08月02日 18:32
 */
public class Lee_503_82 {
    public int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        Deque<Integer> deque = new ArrayDeque<>();
        int[] res = new int[len];
        Arrays.fill(res, -1);

        for (int i = 1; i <= 2 * len - 1; i++) {
            int index = i % len;
            if (deque.isEmpty()) {
                deque.offer(index);
            } else {
                // 如果当前元素大于队伍尾巴
                if (nums[index] > nums[deque.peekLast()]){
                    while (!deque.isEmpty() && nums[index] > nums[deque.peekLast()]){
                        res[deque.pollLast()] = nums[index];
                    }
                }
                deque.offer(index);
            }
        }
        return res;
    }
}
